package leecode

import (
	"strconv"
)

func crackPassword(password []int) string {
	quickSortLCR(password, 0, len(password)-1)
	var result string
	for i := 0; i < len(password); i++ {
		result += strconv.Itoa(password[i])
	}
	return result
}

func quickSortLCR(password []int, start, end int) {
	if start >= end {
		return
	}
	p := password[start]
	i, j := start, end
	for i < j {
		for i < j && quickHelper(password[j], p) {
			j--
		}
		password[i] = password[j]
		for i < j && quickHelper(p, password[i]) {
			i++
		}
		password[j] = password[i]
	}
	password[i] = p
	quickSortLCR(password, start, i-1)
	quickSortLCR(password, i+1, end)
}

func quickHelper(a, b int) bool {
	strA, strB := strconv.Itoa(a), strconv.Itoa(b)
	if strA+strB >= strB+strA {
		return true //a大
	}
	return false //a小,符合条件
}

/*
func greater(a, b string) bool {
	return a+b >= b+a
}

func quickSort(s []string) {
	if len(s) == 0 || len(s) == 1 {
		return
	}
	left, right := 0, len(s)-1
	split := 0
	for left != right {
		for left < right && greater(s[split], s[right]) {
			right--
		}
		for left < right && greater(s[left], s[split]) {
			left++
		}
		s[left], s[right] = s[right], s[left]
	}
	s[left], s[split] = s[split], s[left]
	quickSort(s[:left])
	quickSort(s[left+1:])
}
*/
